/**
 * Created with IntelliJ IDEA.
 * Description:模拟实现LinkedList
 * User: LianBao
 * Date: 2024-03-29
 * Time: 20:32
 */
//不带头 双向 非循环 链表
public class myLinkedList<T> {

    //结点类
    static class ListNode {
        public ListNode prev;//前驱
        public Object val;//数据
        public ListNode next;//后继

        //构造方法
        public ListNode(Object val) {
            this.val = val;
        }
    }

    public ListNode first;//第一个结点
    public ListNode last;//最后一个结点

    //头插法
    public void addFirst(T val) {
        ListNode newNode = new ListNode(val);
        //如果没有元素
        if (first == null) {
            first = last = newNode;
            return;
        }
        newNode.next = first;
        first.prev = newNode;
        first = newNode;
    }

    //尾插法
    public void addLast(T val) {
        ListNode newNode = new ListNode(val);
        //如果没有元素
        if (last == null) {
            first = last = newNode;
            return;
        }
        newNode.prev = last;
        last.next = newNode;
        last = newNode;
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, T val) {
        ListNode newNode = new ListNode(val);
        //index合法性检查
        try {
            if (index < 0 || index > size()) {
                throw new IndexNotLegalException("Index不合法");
            }
        } catch (IndexNotLegalException e) {
            e.printStackTrace();
        }

        //index=0 头插
        if (index == 0) {
            addFirst(val);
            return;
        }
        //index=size 尾插
        if (index == size()) {
            addLast(val);
            return;
        }
        //
        ListNode cur = first;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        ListNode prev = cur.prev;
        //开始绑定
        newNode.next = cur;
        newNode.prev = prev;
        prev.next = newNode;
        cur.prev = newNode;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(T key) {
        if (first == null) {
            return false;
        }
        ListNode cur = first;
        while (cur != null) {
            if (cur.val.equals(key)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //删除第一次出现关键字为key的节点
    public void remove(T key) {
        if (first == null) {
            return;
        }
        //
        ListNode del = first;
        while (del != null) {
            if (del.val.equals(key)) {
                //删除
                ListNode pre = del.prev;
                ListNode next = del.next;
                //pre==null?
                if (pre == null) {
                    //第一个是key
                    first = first.next;
                    return;
                }
                if (next == null) {
                    //最后一个是key
                    last = last.prev;
                    last.next = null;
                    return;
                }
                pre.next = next;
                next.prev = pre;
                return;
            }
            del = del.next;
        }
    }

    //删除所有值为key的节点
    public void removeAllKey(T key) {
        if (first == null) {
            return;
        }
        //处理前面的key
        while (first.val.equals(key)) {
            first = first.next;
            if (first == null) {
                return;
            }
        }
        while (last.val.equals(key)) {
            last = last.prev;
            last.next = null;
        }
        //
        ListNode del = first;
        while (del != null) {
            if (del.val.equals(key)) {
                //删除
                ListNode pre = del.prev;
                ListNode next = del.next;
                //
                pre.next = next;
                next.prev = pre;
            }
            del = del.next;
        }
    }

    //得到单链表的长度
    public int size() {
        int size = 0;
        ListNode cur = first;
        while (cur != null) {
            cur = cur.next;
            size++;
        }
        return size;
    }

    public void clear() {
        while (first != null) {
            ListNode next = first.next;
            first.prev = first.next = null;
            first = next;
        }
        last = null;
    }
}